//package org.example.leetcpde;
//
//import org.junit.jupiter.api.Test;
//
//import java.util.ArrayList;
//import java.util.List;
//
//public class solveNQueens {
//    @Test
//    void run() {
//        List<List<String>> lists = solveNQueens(4);
//    }
//
//
//    public List<List<String>> solveNQueens(int n) {
//
//        List<List<String>> res = new ArrayList<>();
//        boolean[] x = new boolean[(n << 1) + 1];
//        boolean[] y = new boolean[(n << 1) + 1];
//        boolean[] z = new boolean[n];
//
//        dfs(new ArrayList<>(), res, x, y, z, n);
//        return res;
//    }
//
//    void dfs(List<String> cur,
//             List<List<String>> res,
//             boolean[] x,
//             boolean[] y,
//             boolean[] z,
//             int n) {
//        int i = cur.size();
//        if (i == n) {
//            res.add(new ArrayList<>(cur));
//            return;
//        }
//
//        for (int j = 0; j < n; j++) {
//            int xIdx = i - j + n, yIdx = i + j;
//            if (z[j] || x[xIdx] || y[yIdx]) {
//                continue;
//            }
//
//            StringBuilder builder = new StringBuilder();
//            builder.repeat(".", n);
//            builder.replace(j, j + 1, "Q");
//            cur.add(builder.toString());
//
//            x[xIdx] = y[yIdx] = z[j] = true;
//
//            dfs(cur, res, x, y, z, n);
//            x[xIdx] = y[yIdx] = z[j] = false;
//            cur.remove(cur.size() - 1);
//        }
//    }
//}
